17 Bit Software 3: The Continuation/17-Bit_The_Continuation_Disc.iso/amigan/amigan 21/recursion/on_recursion.txt

Text File | 1994-01-27 | 7.5 KB | 115 lines

  A Summary of the Barnes-Butterfield War    In all innocence, we wrote a short
     YOU CAN SO RECURSE IN AMIGA BASIC       article in Vol. III, No. 2, to de-
                   AND,                      monstrate recursion for an Amigan
         INSIGHTS INTO THE FOLLIES           who asked what it involved. In that
         OF BRUTE FORCE RECURSION            article, we said you can't "use re-
                                             cursion" in Amiga Basic. Not long
after, a letter arrived, addressed to "The Hater and Vilifier of Amiga Basic, PO
Box 411..." The Postmistress handed it to us and said, "Better tone down what-
ever it is you're writing, Dick. We're getting tired of checking the hate-mail
for letter bombs." (Most of the hate mail arrives from software houses who fail
to appreciate our comments on their programs).

 But this wasn't hate mail. In his usual calm, precise way, Jim Butterfield told
us we could recurse in Amiga Basic with GOSUB, and demonstrated how. He also up-
held the honor and utility of that language with many a good example. Last, he
warned that brute force recursion on a knight's tour of a full 8 x 8 board might
require half of forever. We replied at length, expounding upon the many virtues
of True Basic, and objecting that GOSUB did not allow passage of arguments dur-
ing recursion. (This began as a "my language is better than your language" sort
of thing, from which both of us soon had the good sense to desist.)<

 One rainy afternoon, in about two hours, we wrote a simple True Basic program
to demonstrate recursion in action as the program attempted to solve a 4 x 4
board. We sent it to Jim because it was short and showed graphically each recur-
sive move. We also sent a copy to old master Terry Peterson in California, and
asked if he could adapt it to A/C Basic (the compiled version), for, if memory
served, A/C Basic could accept recursive subroutine calls with arguments.<

  Terry Peterson responded first, with a much-improved recursive version of our
program, in A/C Basic, which ran about twice as fast as ours did. It showed that
A/C Basic indeed recursed with efficiency and speed. Okay, Basic wins the first
battle of the war. Then Jim wrote a thoughtful letter, noting the overwhelming
follies of plain, brute-force recursion. Following are a few of his ideas, which
we demonstrate on a 5 x 5 board:

    1  0  3  8  0       `MISSED CORNERS:`Only two ways into and out of a corner
    0  13 6  0  4        exist. If you you use one to get there, you must use
    0  2  9  12 7        the other to leave. At left, the moves around the upper
    0  11 0  5  0        right corner ignore the rule. Move 13 could make the
    0  0  0  10 0        corner, but leave no way out. When such corners don't
                         fill properly, a recursive program wastes an enormous
amount of time to learn that the board can't be solved until it backs off and
makes the appropriate moves into and out of each corner. (Yes, a 5 x 5 board can
be solved).

    1  6  3  12 9       `TRAPS at MISSED SQUARES:`At left sit two blank squares,
    4  11 8  0  0        in positions 5 and 6, row 2. Move 14 made it impossible
    7  2  5  10 13       for either to be reached; move 15 blocks the knight ut-
    0  15 0  0  0        terly. As you watch a knight move recursively, you can
    0  0  0  14 0        see these traps develop.

There are two obvious mechanical solutions: 1) develop algorithms able to fill
corners with logic, and 2) to look ahead and avoid the traps at missed squares.
No one, so far as we know, has written such routines. Indeed, there's no assur-
rance that they'd be faster than brute force recursion.

`Jim Butterfield, with his usual ingenuity,`asked why the viewer can't intervene
when these obvious problems develop. He wrote two programs in Amiga Basic which
let you intervene at will, back off to a specific move, and try again. We find
ourselves fascinated, as we use Jim's programs, with learning how to look at a
board and back off to a move that'll unblock a board and let the knight proceed.
Both are written for full 8 x 8 boards (Jim told us that REAL MEN do not horse
around with 4 x 4 boards, even for demos. We've been eating quiche ever since.)<

The war was not without its lighter moments. Jim conceived a grand scheme based
on symmetry. "Aha," he said, "a search to depth of 64 is a great time waster.
With symmetry, could this not be reduced to 16? If I could find a pattern of 16
moves that took me from upper-left to upper-right, I could iterate these moves
(rotatated 90 degrees) to get to lower-right, etc. It wasn't hard to code, but
I wondered why no useful solutions appeared. Then it struck me! THERE CAN BE
NO POSSIBLE SOLUTION! Proof: On each move, a knight moves to a square of oppos-
ite color. Each two-move pair, the knight returns to to the original color. Af-
ter 16 moves, the knight must be on the same color it started. But--upper left
and upper right corners have opposite colors! There is no way 16 moves can get
from one to the other. Reductio ad absurdum. Groan..."

Jim adds, "Can we do a 32-move sequence that repeats, upper left to lower right?
It takes more time than you might think, and again is helped by manual interven-
tion."

`Doug Jones of Atlantic Highlands`also sent us a recursive tour in C; it works
(swiftly!) on boards from 4 x 4 to 8 x 8. It states "no answer" to a 4 x 4 board
in 16 seconds, solves a 5 x 5 board in less than 1 second, solves a 6 x 6 board
in 9 minutes 45 seconds, and (suprise!) finds a solution to a 7 x 7 in 6:35. It
prints a blue and white checkerboard on screen, and shows recursion by move num-
ber on the board (it's pretty swift at that). We set it up this morning on our
A-1000 with nothing else running, looking for a solution to an 8 x 8 board...<

`The Object of our Exercise in Recursion`is to demonstrate how it works. Those
who want to see it in both source code and action will find all the programs on
Amigan PD Disk 21. Terry Peterson placed the A/C version in the runtime package
so that anyone can run it. The A/C Basic programs--as well as Jim's--graphically
represent the board for each move; the effect of recursion is plain as the nose
on an elephant. The source code for Doug Jones' C program is an excellent demo
in that language, although the recursive work is graphically so swift it's al-
most impossible to follow.

`Some numbers will make the weaknesses in brute force recursion come alive.`We
ran both A/C Basic and True Basic on 8 x 8 boards for over half a billion iter-
ations without finding a solution. With manual intervention, one can find a sol-
ution to an 8 x 8 board with Jim's program and no practice in less than a hour.
The weakness in a brute force approach is amply demonstrated by Doug Jones' pro-
gram in C. We kicked it off on an 8 x 8 board at 11:59 on Friday morning, and at
23:59 had to shut it down--still not solved. Jim's comments about the stupidity
of brute force recursion were amply demonstrated here. The move sequence at the
            left appeared shortly after 1 p.m. on the lower-left hand corner of
  13  4     the board. The program spent the next ten hours on recursive moves
  0   19    higher than and beyond this obvious failure. In time, it would have
            backtracked down the recursive road and filled the corner. But--in
how many more hours (or days)? Brute force recursion on complex problems, as Jim
said at the beginning, demands either clever auxiliary algorithms or manual in-
tervention--or both. If you want to understand recursion and how it works, its
weaknesses and strengths, you can do no better than read and run the programs
issued on PD Disk 21.